package medium;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/9/21 9:24
 */
public class No36_有效的数独 {
    public static void main(String[] args) {
        Solution36 solution36 = new Solution36();
        char[][] board = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        boolean validSudoku = solution36.isValidSudoku(board);
        System.out.println(validSudoku);
    }
}

class Solution36 {
    public boolean isValidSudoku(char[][] board) {
        //使用数组,实现一次遍历判断
        //行数
        int x = board.length;
        //列数
        int y = board[0].length;
        
        //行数组
        boolean[][] xCheck = new boolean[9][9]; //false
        //列数组
        boolean[][] yCheck = new boolean[9][9]; //false
        //框数组
        boolean[][] kCheck = new boolean[9][9]; //false
        
        for (int i = 0; i < x; i++) { //i:x
            for (int j = 0; j < y; j++) {//j:y
                //假定x=3,则获取3索引位置的数组,将值放入对应数组索引
                //[x][board[i][j]-'1']
                //考虑去重复问题
                //1.去重复:计数法,如果相同值+1,如果个数>1,则重复
                //2.boolean判断,如果有值,标记true,如果是true,则重复

                int index = i / 3 * 3 + j / 3;
                if (board[i][j] != '.') {
                    if (xCheck[i][board[i][j] - '1'] ||
                            yCheck[j][board[i][j] - '1'] ||
                            kCheck[index][board[i][j] - '1']) {
                        return false;
                    }
                    
                    xCheck[i][board[i][j] - '1'] = true;
                    yCheck[j][board[i][j] - '1'] = true;
                    kCheck[index][board[i][j] - '1'] = true;
                }
                
            }
        }
        return true;
    }
}



    //public boolean isValidSudoku(char[][] board) {
    //    //暴力法
    //    int x = board[0].length;
    //    int y = board.length;
    //    //set
    //    Set<Character> hangSet = new HashSet<>();
    //    Set<Character> lieSet = new HashSet<>();
    //    
    //    //框Set
    //    List<Set<Character>> kuangList = new ArrayList<>();
    //    for (int i = 0; i < x; i++) {
    //        kuangList.add(new HashSet<>());
    //    }
    //    
    //    //处理行,列
    //    for (int i = 0; i < x; i++) {
    //        //清空!以便下次判断
    //        hangSet.clear();
    //        lieSet.clear();
    //        for (int j = 0; j < y; j++) {
    //            //行列值获取
    //            char hangNum = board[i][j];
    //            char lieNum = board[j][i];
    //            
    //            //去重判断?
    //            if (hangNum != '.') {
    //                //可以加
    //                if (!hangSet.add(hangNum)) {
    //                    return false;
    //                }
    //            }
    //
    //            if (lieNum != '.') {
    //                //可以加
    //                if (!lieSet.add(lieNum)) {
    //                    return false;
    //                }
    //            }
    //        }
    //    }
    //    
    //    //处理框
    //    for (int i = 0; i < x; i++) {
    //        for (int j = 0; j < y; j++) {
    //            //框索引获取
    //            //x每走3个,索引+1
    //            //y每走3个,索引+3
    //            int index = j / 3 * 3 + i / 3;
    //            //获取值,扔入对应list位置的set,看它是否可加
    //            if (board[i][j] != '.') {
    //                if (!kuangList.get(index).add(board[i][j])) {
    //                    return false;
    //                }
    //               
    //            }
    //        }
    //    }
    //    return true;
    //}
